This invention relates to routing of data communication using virtual channels.
An interconnected system may include nodes and communication links joining the nodes. In general, each link between nodes may support a number of independent channels, for example, each with its own dedicated buffers and other resources. The communication approach used on the channels can involve deterministic or non-deterministic routing, such as adaptive routing. In deterministic routing, a message arriving over a channel at a node is deterministically passed to a particular outbound channel to reach its destination. For example, such deterministic routing is based on the ultimate destination node of the message. In non-deterministic routing, the choice of outbound channel may depend on (i.e., adapt to) characteristics of the system, such as the backlog in queues used to service the various channels, or otherwise follow routes that are not a deterministic function of the network topology. In some implementations, adaptive routing may provide performance advantages over deterministic routing, for example, by making better use of available resources.
In many systems an important characteristic of a communication approach for passing data between the nodes is that the system cannot reach a deadlock, which is referred to as the system being “deadlock-free.” For instance, it is important that the communication requests cannot result in a situation in which resources that are required to satisfy the request cannot be freed until that same request is satisfied.
In one approach, given a set of nodes and links joining the nodes, in order to achieve deadlock-free behavior a number of channels are defined for each link, referred to as “virtual channels.” A deterministic routing approach is defined on the nodes and the set of virtual channels. For particular interconnection topologies of nodes, arrangements of virtual channels to support deadlock-free deterministic routing are known or can be derived using conventional approaches. An approach to introducing virtual channels for deadlock avoidance is described in William J. Dally, “Deadlock-Free Message Routing in Multiprocessor Interconnection Networks,” IEEE Trans. on Computers, Vol. C-36, No. 5, May 1987, pp. 547-553.
One approach to providing adaptive routing while also guaranteeing that the system is deadlock-free is described in José Duato, “A Necessary and Sufficient Condition for Deadlock-Free Routing in Cut-Through and Store-and-Forward Networks,” IEEE Trans. On Parallel and Distributed Systems, Vol. 7, No. 8, August 1996, pp. 841-854. One approach suggested by Duato is to start with a deadlock-free routing approach and then introduce additional virtual channels, for example, by splitting each channel into a set of two channels. The additional channels are then used for adaptive routing. If all the additional channels are busy (i.e., blocked waiting for resources), then only the original channels are used.